#include <iostream>
#include <stdlib.h>
#include <time.h>

using namespace std;


// 希尔排序(从小到大)
// 1.根据size 设置增量gap
// 2.将数组按照gap分组，对每组进行插入排序
// 3.缩小增量（gap /= 2），重复2
// 4.直到gap为0，此时数组已经有序


// 时间和空间复杂度
// 时间复杂度：O(n^2)
// 平均时间复杂度：O(n^1.3)
// 空间复杂度：O(1)
// 最优时间复杂度：O(n) 
// 不稳定
// 由于使用 gap 进行分组，可能把相同的val值分到不同的组

void ShellSort(int arr[], int len)
{
    // 默认第一个元素是有序的
    for (size_t gap = len / 2; gap > 0; gap /= 2)
    {
        for (size_t i = gap; i < len; i++)
        {
            int val = arr[i];
            size_t j = i;
            // 将比val大的元素向后移动
            while (j >= gap && arr[j-gap] > val)
            {
                arr[j] = arr[j-gap];
                j -= gap;
            }
            arr[j] = val;
        }
    }
}

// int main(int argc, const char** argv) {
//     int arr[10];
//     srand(time(NULL));
//     for (int i = 0; i < 10; i++) {
//         arr[i] = rand() % 100;
//         cout << arr[i] << " ";
//     }
//     cout << endl;

//     ShellSort(arr, 10);
//     for (int val : arr)
//         cout << val << " ";
//     cout << endl;
//     return 0;
// }